package 滑动窗口技巧与相关题目;

import java.util.Arrays;

// 至少有K个重复字符的最长子串
// 给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串
// 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度
// 如果不存在这样的子字符串，则返回 0。
// 测试链接 : https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/

public class Code07_LongestSubstringWithAtLeastKRepeating {

    public static int longestSubstring(String str, int k) {
        char[] s = str.toCharArray();
        int n = s.length;
        // 词频统计：这里只使用26个位置
        int[] cnts = new int[256];
        int ans = 0;
        // 26种（a-z）情况：每次要求子串必须含有require种字符，
        // 每种字符的词频都必须>=k次，这样的最长子串是多长
        for(int required = 1; required <= 26; required++){
            // 初始化：每个字符的词频都为0
            Arrays.fill(cnts, 0);
            // collect : 窗口中一共收集到的字符种类数
            // satisfy : 窗口中字符的个数达标的种类数(次数>=k)
            for(int l = 0, r= 0, satify = 0, collect = 0; r < n; r++){
                // r位置的字符加入到词频统计
                cnts[s[r]]++;
                // 说明r位置的字符是第一次进行词频统计，即新的字符，collect++
                if(cnts[s[r]] == 1){
                    collect++;
                }
                // 说明r位置的字符的词频个数 = k
                if(cnts[s[r]] == k){
                    satify++;
                }
                // l....r 种类超了！
                // l位置的字符，窗口中吐出来！
                while (collect > required){
                    // 缩短窗口之前：l位置的字符的词频为1
                    if(cnts[s[l]] == 1){
                        collect--;
                    }
                    if(cnts[s[l]] == k){
                        satify--;
                    }
                    // 缩短窗口
                    cnts[s[l++]]--;
                }
                // l.....r : 子串以r位置的字符结尾，且种类数不超的，最大长度！
                if(satify == required){
                    ans = Math.max(ans, r - l + 1);
                }
            }
        }
        return ans;
    }
}
